A codeword for a general two dimensional (2-D) (N,K) product code is arranged as illustrated in FIG. 1 below. N represents the codeword length while K represents the information length (e.g., number of information symbols or bits, length of the information sequence). A representative block product code codeword comprises Ny rows of constituent code x (labeled “Code x”) codewords and Nx columns of constituent code y (labeled “Code y”) codewords. Code x is a (Nx,Kx) code, Code y is a (Ny,Ky) code, N=Nx×Ny, and K=Kx×Ky. The 2-D block product code codeword 100 can be partitioned into four sub-rectangles, 110, 120, 130, and 140. In FIG. 1, the K-bit input information sequence is denoted by si, for i=0, . . . , K−1, while a parity bit is denoted by pij for i=0, . . . , Ky−1 and j=Kx, . . . , Nx−1, and for i=Ky, . . . , Ny−1 and j=0, . . . , Kx−1. Product codes are also called block product codes (“BPCs”), block turbo codes, and block product turbo codes in the art. When soft information is processed by the block product code decoder, the decoder is sometimes called a block product turbo decoder and block turbo decoder in the art.
Though a maximum likelihood (ML) decoder theoretically provides the best (optimal) performance for decoding block product codes, the ML decoder for block product codes is generally impractical due to its complexity. One low complexity sub-optimal (non-ML) technique using hard-decision decoding of the constituent codes of the block product code is based on iterative techniques but this sub-optimal technique has poor performance. Recently, another sub-optimal technique for decoding block product codes was developed. The decoding can be performed iteratively using soft-input soft-output (SISO) constituent decoders operating on constituent codewords. A soft-input for the subsequent decoding phase may be computed using the soft-output from the current decoding phase in a similar manner to the decoding process for turbo codes. A decoding iteration can be divided into decoding phases as illustrated below. This iterative structure allows the constituent decoders of different dimensions to share information. For example, for the 2-D code illustrated in FIG. 1, the block product codeword is Ny codewords to Code x, while simultaneously it is Nx codewords to Code y. Therefore, both constituent decoder for Code x and constituent decoder for Code y can decode and generate information for the entire codeword. The information generated by the constituent decoders in one dimension can be passed to the constituent decoders in the other dimension together with the received signal, so that a better decoding decision can be made than if only the received signal is used.
While the optimal ML constituent decoder theoretically provides the best performance, its complexity is often impractical for constituent decoding. As a result, sub-optimal decoding techniques such as those employing Chase decoding that approximate the ML constituent decoder are attractive. A Chase decoder is one example of a soft-input soft-output (SISO) decoder for a constituent decoder. Upon receiving the soft-input vector for a (n, k) constituent block code, a binary vector Y and a set of test patterns are formed in the Chase decoder.
A hard-decision decoder, often a bounded-distance decoder, is used to decode each Xi=(Y+Zi) binary vector, where Zi denotes a member of the set of test patterns and for binary codes, the “+” can represent an exclusive-or operation. The hard-decision decoder can either produce a valid codeword or declare a decoding failure. Each valid codeword Ci resulting from decoding (Y+Zi) is saved into a set S. A metric associated with each valid codeword is also saved. The Chase decoder attempts to generate a soft-output for every bit position j by finding the metric difference between two codewords in S, one codeword being the most-likely codeword D and the other being a best competing codeword Cj which differs from D at position j, 1≦j≦n.
A flowchart 200 of the existing method of Chase decoding is shown in FIG. 2. Block 210 finds the L least reliable positions over a portion of the soft-input vector. Block 220 constructs a number of test patterns. In this example, 2L test patterns are constructed. A Chase-L decoder uses 2L test patterns. A loop index i is initialized to 1 in block 230. In block 240 within the loop, a hard-decision decoding of the binary vector (Y+Zi) is performed. If the hard-decision decoding finds a codeword, that codeword is saved to the set S and a corresponding metric is saved. The loop index i is incremented in block 242. A decision whether the loop index i less than or equal to the number of test patterns (in this case 2L) is made in block 245. If Yes, the loop 240-242 is repeated. If No, the soft-output vector is then generated based on the codewords in S and the associated metrics in block 250.
To meet decoding complexity constraints while ensuring adequate performance, the number of test patterns is kept small. However, when the hard-decision decoder declares a decoding failure for many of the test patterns, only a few codewords exist in S. As a result, a large number of positions in the soft-output vector will have inaccurate (or unavailable) soft-output values. For a block turbo decoder using a Chase decoder as a constituent decoder, it is desirable to have accurate soft-output values (and to have soft-output values for each position in a soft-output vector). One method to increase the number of codewords in S is to examine more test patterns. However, the Chase-(L+1) decoder has twice as many test patterns as the Chase-L decoder due to the exponential relationship between L and the number of test patterns, and doubling the number of test patterns within the constituent decoder can nearly double the complexity of the block turbo decoder.
Besides complexity, another problem for block product code decoding is the need to have a common decoder architecture capable of supporting various combinations of constituent codes for a block product code. In examining some of the codes in the ANSI/TIA-902.BAAD standard, there are 3-D block product codes as well as 2-D block product codes with non-identical constituent codes in each dimension. Further, there is a need to have a good performing (e.g., measured by low error rates) generic block turbo decoder.